#
# openlookup/lib/meter.py
#
# Copyright 2008-2009 Helsinki Institute for Information Technology
# and the authors.
#
# Authors: Ken Rimey <rimey@hiit.fi>
#

# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

"""
Rate Meter

A rate meter converts an ongoing sequence of samples of a
monotonically increasing value into an estimate of the rate of
increase of the value.

Simply call update() from time to time with a new value, which must be
no less than the previous value.  The method get_rate() will return an
estimate of the rate of increase during the last 5 seconds prior to
the last call to update().
"""

import time
from collections import deque

class Meter(deque):
    def __init__(self, interval=10.0):
        self.interval = interval
        self.rate = 0

    def update(self, value, now=None):
        now = now or time.time()

        if self:
            last_time, last_value = self[-1]
        else:
            last_time = last_value = 0

        assert last_value <= value
        if last_time < now:
            self.append((now, value))

            # Keep only enough samples to cover the interval of interest.
            while len(self) > 2 and self[1][0] <= now - self.interval:
                self.popleft()

            self.rate = self._get_rate()

    def get_rate(self, unit=1, precision=1):
        # Can be called concurrently.
        return round(self.rate / unit, precision)

    def _get_rate(self):
        if len(self) < 2:
            return 0

        t0, v0 = self[0]
        t1, v1 = self[1]
        t2, v2 = self[-1]

        start = max(t0, t2 - self.interval)
        assert t0 <= start < t1 <= t2

        fraction = float(t1 - start) / (t1 - t0)
        assert 0 < fraction <= 1

        increase = (v1 - v0) * fraction + (v2 - v1)
        return increase / (t2 - start)

if __name__ == '__main__':
    class Test(Meter):
        def __init__(self, v, t):
            Meter.__init__(self, interval=5.0)
            self.v = v
            self.t = t

        def step(self, dv, dt, expected_rate):
            self.v += dv
            self.t += dt
            self.update(self.v, self.t)
            assert self.get_rate() == expected_rate

    m = Test(100, 1000)
    assert m.get_rate() == 0

    m.step(0, 0, 0)
    m.step(10, 1, 10)
    m.step(90, 3, 25)
    m.step(0, 1, 20)
    m.step(60, 1, 30)
    m.step(30, 1, 30)
    m.step(1, 5, 0.2)
    m.step(1, 2.5, 0.3)
    m.step(1, 10, 0.1)

    print 'OK'
